121. 买卖股票的最佳时机

Similar Question

Solution Tips

方案一: 暴力法

public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}

方案二: 贪心

保留当前遍历到的最小值, 不断的获取与当前遍历到的值的差值.

遇到了新的最小值, 就直接切换成新的最小值即可. 因为再出现更大的值, 也是与最小值的差才是最大的

var maxProfit = function(prices) {
    let lowerPrice = prices[0];// 重点是维护这个最小值（贪心的思想） 
    let profit = 0;
    for(let i = 0; i < prices.length; i++){
        lowerPrice = Math.min(lowerPrice, prices[i]);// 贪心地选择左面的最小价格
        profit = Math.max(profit, prices[i] - lowerPrice);// 遍历一趟就可以获得最大利润
    }
    return profit;
};

对方法二的另一种解释： 方法二可以看做一种动态规划，只不过对空间复杂度进行了优化。考虑每次如何获取最大收益？第 i 天的最大收益只需要知道前 i 天的最低点就可以算出来了。而第 i 天以前（包括第 i 天）的最低点和 i-1 天的最低点有关，至此我们的动态方程就出来了。

dp[i] = min(dp[i-1], prices[i])

其中 dp[0]=prices[0],然后动态计算之后的就可以了。 得到了前 i 天的最低点以后，只需要维护一个 max 用来保存最大收益就可以了。 这个时候是空间复杂度 O（n）的动态规划，代码如下：

        //dp[i]表示截止到i，价格的最低点是多少   dp[i]=min(dp[i-1],nums[i])
        int max = 0;
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = (dp[i - 1] < prices[i]) ? dp[i - 1] : prices[i];
            max = (prices[i] - dp[i]) > max ? prices[i] - dp[i] : max;
        }
        return max;

接着考虑优化空间，仔细观察动态规划的辅助数组，其每一次只用到了 dp[-1] 这一个空间，因此可以把数组改成单个变量 dp 来存储截止到第 i 天的价格最低点。优化之后的代码就是题解中的方法二。

方案三: 动态规划

放弃, 迷惑的不行